import re

PropIdentRe = re.compile(r"\A[A-Z]{1,8}\\Z")
PropValueRe = re.compile(
    r"\A [^\\\]]* (?: \\. [^\\\]]* )* \Z", re.VERBOSE | re.DOTALL
)
FindStartRe = re.compile(r"\(\s*;")
TokeniseRe = re.compile(
    r"""\s*(?:
    \[ (?P<V> [^\\\]]* (?: \\. [^\\\]]* )* ) \]   # PropValue
    |
    (?P<I> [A-Z]{1,8} )                           # PropIdent
    |
    (?P<D> [;()] )                                # delimiter
    )""",
    re.VERBOSE | re.DOTALL,
)


def IsValidPropertyIdentifier(s: str):
    return bool(PropIdentRe.search(s))


def IsValidPropertyValue(s: str):
    return bool(PropValueRe.search(s))


def Tokenise(s: str, start_pos: int = 0):
    result = []
    m = FindStartRe.search(s, start_pos)
    if not m:
        return [], 0
    i = m.start()
    depth = 0
    while True:
        m = TokeniseRe.match(s, i)
        if not m:
            break
        group = m.lastgroup
        token = m.group(m.lastindex)
        result.append((group, token))
        i = m.end()
        if group == "D":
            if token == "(":
                depth += 1
            elif token == ")":
                depth -= 1
                if depth == 0:
                    break
    return result, i


class CoarseGameTree:
    def __init__(self) -> None:
        self.sequence = []
        self.children = []


def _ParseSgfGame(s: str, start_pos: int = 0):
    tokens, end_pos = Tokenise(s, start_pos)
    if not tokens:
        return None, None
    stack = []
    game_tree: CoarseGameTree = None
    sequence = None
    properties = None
    index = 0
    try:
        while True:
            token_type, token = tokens[index]
            index += 1
            if token_type == "V":
                raise ValueError("Unexpected value")
            if token_type == "D":
                if token == ";":
                    if sequence is None:
                        raise ValueError("Unexpected node")
                    properties = {}
                    sequence.append(properties)
                else:
                    if sequence is not None:
                        if not sequence:
                            raise ValueError("Empty sequence")
                        game_tree.sequence = sequence
                        sequence = None
                    if token == "(":
                        stack.append(game_tree)
                        game_tree = CoarseGameTree()
                        sequence = []
                    else:
                        # token == ')'
                        variation = game_tree
                        game_tree = stack.pop()
                        if game_tree is None:
                            break
                        game_tree.children.append(variation)
                    properties = None
            else:
                # token_type == 'I'
                prop_ident = token
                prop_values = []
                while True:
                    token_type, token = tokens[index]
                    if token_type != "V":
                        break
                    index += 1
                    prop_values.append(token)
                if not prop_values:
                    raise ValueError("Property with no values")
                try:
                    if prop_ident in properties:
                        properties[prop_ident] += prop_values
                    else:
                        properties[prop_ident] = prop_values
                except TypeError:
                    raise ValueError("Property value outside a node")
    except IndexError:
        raise ValueError("Unexpected end of sgf data")
    assert index == len(tokens)
    return variation, end_pos


def ParseSgfGame(s: str) -> CoarseGameTree:
    game_tree, _ = _ParseSgfGame(s, 0)
    if game_tree is None:
        raise ValueError("No sgf data found")
    return game_tree


def ParseSgfCollection(s: str):
    pos = 0
    result = []
    while True:
        try:
            game_tree, pos = _ParseSgfGame(s, pos)
        except ValueError as e:
            raise ValueError(f"Error parsing game {len(result)}: {e}")
        if game_tree is None:
            break
        result.append(game_tree)
    if not result:
        raise ValueError("No sgf data found.")
    return result


def BlockFormat(pieces, width=79):
    lines = []
    line = ""
    for s in pieces:
        if len(line) + len(s) > width:
            lines.append(line)
            line = ""
        line += s
    if line:
        lines.append(line)
    return "\n".join(lines)


def SerialiseGameTree(game_tree: CoarseGameTree, wrap: int=79) -> str:
    l = []
    to_serialise = [game_tree]
    while to_serialise:
        game_tree = to_serialise.pop()
        if game_tree is None:
            l.append(")")
            continue
        l.append("(")
        for properties in game_tree.sequence:
            l.append(";")
            for prop_ident, prop_values in sorted(
                list(properties.items()), key=lambda pair: (-(pair[0] == "FF"), pair[0])
            ):
                m = [prop_ident]
                for value in prop_values:
                    m.append('[' + value + ']')
                l.append(''.join(m))
        to_serialise.append(None)
        to_serialise.extend(reversed(game_tree.children))
    l.append('\n')
    if wrap is None:
        return ''.join(l)
    else:
        return BlockFormat(l,wrap)
    
def MakeTree(game_tree: CoarseGameTree, root, node_builder, node_adder):
    to_build = [(root, game_tree, 0)]
    while to_build:
        node, game_tree, index = to_build.pop()
        if index < len(game_tree.sequence) - 1:
            child = node_builder(node, game_tree.sequence[index+1])
            node_adder(node, child)
            to_build.append((child, game_tree, index+1))
        else:
            node.children = []
            for child_tree in game_tree.children:
                child = node_builder(node, child_tree.sequence[0])
                node_adder(node, child)
                to_build.append((child, child_tree, 0))

def MakeCoarseGameTree(root, get_children, get_properties):
    result = CoarseGameTree()
    to_serialise = [(result, root)]
    while to_serialise:
        game_tree, node = to_serialise.pop()
        while True:
            game_tree.sequence.append(get_properties(node))
            children = get_children(node)
            if len(children) != 1:
                break 
            node = children[0]
        for child in children:
            child_tree = CoarseGameTree()
            game_tree.children.append(child_tree)
            to_serialise.append((child_tree, child))
    return result

def MainSequenceIter(game_tree):
    while True:
        for properties in game_tree.sequence:
            yield properties
        if not game_tree.children:
            break 
        game_tree = game_tree.children[0]

SplitComposeRe = re.compile(r"( (?: [^\\:] | \\. )* ) :", re.VERBOSE | re.DOTALL)

def ParseCompose(s):
    m  = SplitComposeRe.match(s)
    if not m:
        return s, None 
    return m.group(1), s[m.end():]

def Compose(s1:str, s2:str):
    return s1.replace(":", "\\:") + ":" + s2 

NewlineRe = re.compile(r'\n\r|\r\n|\n|\r')

WhitespaceTable = str.maketrans('\t\f\v', '   ')

ChunkRe = re.compile(r" [^\n\\]+ | [\n\\] ", re.VERBOSE)

def SimpleTextValue(s:str):
    s = NewlineRe.sub('\n', s)
    s = s.translate(WhitespaceTable)
    is_escaped = False 
    result = []
    for chunk in ChunkRe.findall(s):
        if is_escaped:
            if chunk != '\n':
                result.append(chunk)
            is_escaped = False
        elif chunk == '\\':
            is_escaped = True
        elif chunk == '\n':
            result.append(' ')
        else:
            result.append(chunk)
    return ''.join(result)

def TextValue(s:str):
    s = NewlineRe.sub('\n', s)
    s = s.translate(WhitespaceTable)
    is_escaped = False 
    result = []
    for chunk in ChunkRe.findall(s):
        if is_escaped:
            if chunk != '\n':
                result.append(chunk)
            is_escaped = False
        elif chunk == '\\':
            is_escaped = True
        else:
            result.append(chunk)
    return ''.join(result)

def EscapeText(s:str):
    return s.replace('\\', '\\\\').replace(']', '\\]')


    